package com.rn.gypsophila.dsalg.arrary;

/**
 * 题目：
 * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
 * 请必须使用时间复杂度为 O(log n) 的算法。
 * 链接：<a href="https://leetcode.cn/leetbook/read/array-and-string/cxqdh/">...</a>
 * 思路：二分法
 * 1.先设定左侧下标 low 和右侧下标 high，再计算中间下标 middle
 * 2.逐次让 nums[middle] 和 target 比较大小,相等则返回下标，小于则 low 右移，大于则 high 左移
 * 3.查找结束如果没有相等值则返回 low
 *
 * @author 然诺
 * @since 2022/8/28
 */
public class SearchInsertIndex {

    /**
     * 二分法，时间复杂度：O(logn)
     * 时间复杂度即是 while 循环的次数：n,n/2,n/4,...n/2^k（接下来操作元素的剩余个数），其中 k 就是循环的次数
     */
    public static int searchInsert(int[] nums, int target) {
        int low = 0;
        int high = nums.length - 1;
        while (low <= high) {
            int middle = (low + high) >>> 1;
            if (nums[middle] == target) {
                return middle;
            } else if (nums[middle] > target) {
                high = middle - 1;
            } else {
                low = middle + 1;
            }
        }
        return low;
    }

    public static void main(String[] args) {
        int[] a1 = new int[]{1, 3, 5, 6};
        System.out.println(searchInsert(a1, 5));
        int[] a2 = new int[]{1, 3, 5, 6};
        System.out.println(searchInsert(a2, 2));
        int[] a3 = new int[]{1, 3, 5, 6};
        System.out.println(searchInsert(a3, 7));
    }

}
